package com.mzy.linear_struct.ks.链表;


import java.util.PriorityQueue;

/**
 * @Author: mizy3
 * @Date: 2024/08/22/上午9:51
 * @Description:
 */
public class 合并K个升序链表 {

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a,b) -> a.val - b.val);
        for (ListNode head : lists) {
            if(head != null){
                pq.offer(head);
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (!pq.isEmpty()){ // 循环直到堆为空
            ListNode node = pq.poll(); // 剩余节点中的最小节点
            if (node.next != null) {
                pq.offer(node.next);
            }
            cur.next = node;
            cur = cur.next;
        }

        return dummy.next;
    }
}
class ListNode {

    int val;
    ListNode next;
    public ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val,ListNode next) { this.val = val; this.next = next; }
}



















